Clique width minimization is NP-hard

Title: Clique width minimization is NP-hard
Creator: Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan
Relation: STOC '06 . Proceedings of the 38th Annual ACM Symposium on Theory of Computing (Seattle, WA, USA May 21-23) p. 354-362
Publisher Link: http://dx.doi.org/10.1145/1132516.1132568
Publisher: ACM Press
Resource Type: conference paper
Date: 2006
Description: Clique-width is a graph parameter that measures in a certain sense the complexity of a graph. Hard graph problems (e.g., problems expressible in Monadic Second Order Logic with second-order quantification on vertex sets, that includes NP-hard problems) can be solved efficiently for graphs of small clique-width. It is widely believed that determining the clique-width of a graph is NP-hard; in spite of considerable efforts, no NP-hardness proof has been found so far. We give the first hardness proof. We show that the clique-width of a given graph cannot be absolutely approximated in polynomial time unless P=NP. We also show that, given a graph G and an integer k, deciding whether the clique-width of G is at most k is NPhy complete. This solves a problem that has been open since the introduction of clique-width in the early 1990s.
Subject: NP-completeness; absolute approximation; clique-width; pathwidth
Identifier: http://hdl.handle.net/1959.13/31715
Identifier: uon:2778
Identifier: ISBN:1595931341
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format